So-called artificial intelligence or pattern-matching programming has been developing and used over the last several years, such as the RETE taught by Forgy. The RETE algorithm is one of several approaches to pattern-matching using set(s) of matching rules. These programs are well known, see the description by Charles L. Forgy in "RETE: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem", ARTIFICIAL INTELLIGENCE, Volume 19, 1982, pp 17-37. Another example of the public knowledge in this area is found in an article by Marshall Schor et al. in "Advances in RETE Pattern Matching", PROCEEDINGS of 1986 AMERICAN ASSOCIATION for ARTIFICIAL INTELLIGENCE CONFERENCE, pp 226-232, 1986. The well known information about RETE networks and artificial intelligence programming is not repeated herein except as needed for one of ordinary skill in this art to understand the present invention. As set forth by Forgy, the network defined as a RETE exhibits certain performance advantages when large numbers of data pattern matches have to be performed. As these networks get larger and more complex, enhancing performance and functionality becomes increasingly important. It is desired to not only enhance performance, but also to enhance functionality of a pattern matching network.
As is well known, such pattern-matching programming executes with a plurality of data structures. A working memory element (WME) is an input data structure. Any new, modified or removed WME results in a "token" (or delta), which is a data structure composed of one or more WMEs together with an associated data operation. Since the current informational content of the RETE does not reflect the WME addition, change or deletion, the RETE needs to be updated by propagating the token through the network such that it reflects the current informational state of the inputs. Each time a token is pushed (processed) through a RETE and is matched with patterns in a RETE constitutes a pattern match operation.
A RETE, as taught by Forgy, consists of alpha and beta portions. When a change token is processed through the RETE, the alpha portion is first traversed after the informational content of a new or changed WME or the informational change resulting from a deleted WME is made available to the network through a "root node". A root node is a data area of the network that is the entry point to the RETE. A set of "top" nodes are connected to the root node. These in turn are connected to successor nodes, finally reaching a plurality of termination or bottom nodes, termed production or match nodes. Each of the node data structures may include match tests for incoming tokens. As known in the art, some of the nodes have memory items to be scanned in a table. These may be implemented as separate nodes, termed "memory nodes", or the tables may be directly associated with nodes representing match operations. The associated memory table for a particular node will be referred to as that node's "result memory". Result memory tables are associated with beta nodes and alpha distribution nodes which will be described later.
The tables for memory items contain values (numeric, text, etc) which represent partial matching results up to that point in the network. These values may be used in subsequent matching operations as one of the inputs to a "join" node. It is to be understood that table accesses follow usual programming procedures and that the matching operations are usual programming effected comparisons.
The alpha portion of a RETE has no result memories, i.e. tables wherein partial pattern matching results are stored; in contrast the beta portion includes such memory tables. In between the alpha and beta portions are nodes called alpha distribution nodes, all of which have result memories which store the partial pattern matching results generated in the alpha portion. From these alpha distribution nodes, the tokens are pushed into the beta portion.
There are two kinds of nodes used in a RETE in terms of the number of input connections: one input nodes and two input nodes. All alpha nodes (as do later described production nodes or match nodes) have one input as do the alpha distribution nodes. We here will refer to such one input as "RHS input" or simply "input". In contrast most beta nodes, except production nodes, match nodes, and other special purpose nodes, have two inputs: left hand side (LHS) and right hand side (RHS) inputs. Such two input nodes are called "join nodes" since token pairs (consisting of input from each side) which pass the join tests (which may be no test at all) are joined together (AND function join nodes as described herein, no limitation thereto is intended), resulting in new amalgamated tokens which are used to update the associated result memory table of the join node.
The RETE algorithm starts with a change token, representing the addition, modification, or deletion of a WME; the program executing the algorithm then scans a plurality of alpha nodes for matching the contents of the change token with match informational items of the respective alpha nodes, as required. That is, each alpha node tests various aspects of the WME as represented by the token, and passes or blocks (does not pass) the token on to various successors of the alpha node. This action continues as is well known in the prior art, until the bottom of the alpha node portion is reached. At this point, assuming the alpha node tests were successful, the first result memory (the alpha distribution node) receives the token, and may update its memory in accordance with the particular WME and operation (add, modify, or delete). On the other hand, if the token testing resulted in test failures (no matches), then the token passing may not extend to the bottom of the alpha portion. The token passing may involve a plurality of logic paths, as is known. Following these pattern matching operations, the beta portion of the RETE continues the RETE operations. For a token arriving at one input of a prototypical beta join node, the node specifies pattern matching functions between the token contents and the set of partially matched tokens contained in the result memory found at a predecessor node logically connected as a source node to the opposite input of the join node. Then the program conducts tests between the token and the result memory as defined in the join node. Such a result memory is termed an "opposite memory".
The RETE is compiled from a set of pattern-matching rules. Each rule defines a logic path through the RETE from the root node to an output node. The rule defined path through a RETE typically becomes quite complex. As a result, as practiced in the prior art, once a RETE is compiled it is a relatively static structure, excepting for updating the result memory tables. It is desired to make a RETE and other pattern matching networks more flexible and changeable.